package pert;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class CriticalPath {
	public static Task[] criticalPath(Set<Task> tasks) {
		HashSet<Task> completed = new HashSet<Task>();
		HashSet<Task> remaining = new HashSet<Task>(tasks);

		while (!remaining.isEmpty()) {
			boolean progress = false;
			for (Iterator<Task> it = remaining.iterator(); it.hasNext();) {
				Task task = it.next();
				if (completed.containsAll(task.getDependencies())) {
					int numCritical = 0;
					for (Task t : task.getDependencies()) {
						if (t.getCriticalCost() > numCritical) {
							numCritical = t.getCriticalCost();
						}
					}
					task.setCriticalCost(numCritical + task.getDuration());
					completed.add(task);
					it.remove();
					progress = true;
				}
			}
			if (!progress)
				throw new RuntimeException("Not acyclic!");
		}

		HashSet<Task> cleaned = new HashSet<Task>(completed);
		for (Task task : completed) {
			if (task.getDependencies().size() > 1) {
				Task higest = new Task();
				for (Task dependency : task.getDependencies()) {
					if (dependency.getDuration() > higest.getDuration()) {
						higest = dependency;
					}
				}
				for (Task eliminate : task.getDependencies()) {
					if (higest.getName().compareTo(eliminate.getName()) != 0) {
						cleaned.remove(eliminate);
					}
				}
			}
		}

		Task[] ret = cleaned.toArray(new Task[0]);

		Arrays.sort(ret, new Comparator<Task>() {

			@Override
			public int compare(Task o1, Task o2) {
				int i = o2.getCriticalCost() - o1.getCriticalCost();
				if (i != 0)
					return i;
				if (o1.isDependent(o2))
					return -1;
				if (o2.isDependent(o1))
					return 1;
				return 0;
			}
		});
		return ret;
	}
}